package hyy_2022;

/**
 * 买卖股票的最佳时机
 */
public class _0709_121_MaxProfit {
    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfitByMyself(prices));
        System.out.println(maxProfitByOfficial(prices));
    }

    /**
     * 我只能想到的暴力解法
     * @param prices  它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
     * @return 获取的最大利润
     */
    public static int maxProfitByMyself(int[] prices) {
        int maxProfit = 0;
        for(int i=0;i<prices.length-1;i++) {
            for(int j=i+1;j<prices.length;j++) {
                int profit = prices[j] - prices[i];
                if(profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }

    /**
     * 看了官方题解的思路,然后自己敲出来
     * 用一个变量记录历史最低点价格,然后往前推移,不断获取历史最低点以及最大利润
     * @param prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
     * @return 获取的最大利润
     */
    public static int maxProfitByOfficial(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for(int i=0;i<prices.length;i++) {
            if(prices[i] < minPrice) {
                //记录历史最低点价格
                minPrice = prices[i];
            } else {
                //数组往前推移,不断计算最大利润
                if(prices[i] - minPrice > maxProfit) {
                    maxProfit = prices[i] - minPrice;
                }
            }
        }
        return maxProfit;
    }
}
